﻿// Copyright 2007-2008 Rory Plaire (codekaizen@gmail.com)

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Runtime.InteropServices;
using NPack.Interfaces;

namespace NPack
{
    /// <summary>
    /// Defines a vector buffer for storing vector data in a specific format. The 
    /// <see cref="ManagedVectorBuffer{TVector, TComponent}"/> stores vectors
    /// on the managed heap, and is fully verifiable.
    /// </summary>
    /// <typeparam name="TVector">The type of vector to store.</typeparam>
    /// <typeparam name="TComponent">The type of component in the vector.</typeparam>
    /// <remarks>
    /// <para>
    /// A vector buffer allows specific storage of vectors in memory. This is useful
    /// since modern hardware treats vector data specially, and a specific storage
    /// format can take advantage of these capabilities. For example, SSE and SSE2 instructions
    /// are found on almost all of the non-embedded, general-purpose CPUs on the market,
    /// and these instructions work best when memory is aligned to 16-byte boundaries. 
    /// Using a Structure of Arrays (SoA) data format is also preferable when performing
    /// matrix computations.
    /// </para>
    /// </remarks>
    public class ManagedVectorBuffer<TVector, TComponent> : IVectorBuffer<TVector, TComponent>
        where TVector : IBufferedVector<TVector, TComponent>, IEquatable<TVector>, IComparable<TVector>, IComputable<Double, TVector>
        where TComponent : IEquatable<TComponent>, IComparable<TComponent>, IComputable<TComponent>, IConvertible, IFormattable
    {
        private readonly Boolean _isComponentValueType = typeof(TComponent).IsValueType;
        private readonly Boolean _isVectorValueType = typeof(TVector).IsValueType;
        private static readonly Int32 LargeObjectSizeInBytes = 85000;
        private readonly Int32 _homogenousComponentCount;
        private readonly Int32 _vectorDimension;
        private readonly IBufferedVectorFactory<TVector, TComponent> _vectorFactory;
        private Int32 _maxSize;
        private TComponent[] _components;
        private Int32 _nextVectorIndex;
        private readonly LinkedList<Int32> _vectorIndexFreeList = new LinkedList<Int32>();
        private readonly TComponent _one;

        /// <summary>
        /// Creates a new <see cref="ManagedVectorBuffer{TVector, TComponent}" />
        /// for vectors of size <paramref name="vectorDimension"/>, including space 
        /// for an extra component if <paramref name="isHomogeneous"/> is <see langword="true"/>. 
        /// The initial capacity of the created buffer places it in the CLR's Large Object Heap.
        /// </summary>
        /// <param name="vectorDimension">The size, or number of components, of each vector.</param>
        /// <param name="isHomogeneous">
        /// <see langword="true"/> if the vector is represented in homogeneous coordinates 
        /// (allowing affine transforms through matrix operations).
        /// </param>
        /// <param name="vectorFactory">
        /// A factory used to create vectors of type <typeparamref name="TVector"/>.
        /// </param>
        public ManagedVectorBuffer(Int32 vectorDimension,
                                   Boolean isHomogeneous,
                                   IBufferedVectorFactory<TVector, TComponent> vectorFactory)
            : this(vectorDimension, isHomogeneous, vectorFactory,
                vectorDimension == 0
                    ? 0
                    : LargeObjectSizeInBytes / (Marshal.SizeOf(typeof(TComponent)) * vectorDimension) + vectorDimension)
        { }

        /// <summary>
        /// Creates a new <see cref="ManagedVectorBuffer{TVector, TComponent}" /> with
        /// initial capacity <paramref name="initialCapacity"/> for vectors of size
        /// <paramref name="vectorDimension"/>, including space for an extra component
        /// if <paramref name="isHomogeneous"/> is <see langword="true"/>. 
        /// </summary>
        /// <param name="vectorDimension">The size, or number of components, of each vector.</param>
        /// <param name="isHomogeneous">
        /// <see langword="true"/> if the vector is represented in homogeneous coordinates 
        /// (allowing affine transforms through matrix operations).
        /// </param>
        /// <param name="vectorFactory">
        /// A factory used to create vectors of type <typeparamref name="TVector"/>.
        /// </param>
        /// <param name="initialCapacity">The initial capacity for the buffer.</param>
        public ManagedVectorBuffer(Int32 vectorDimension, Boolean isHomogeneous,
                                   IBufferedVectorFactory<TVector, TComponent> vectorFactory,
                                   Int32 initialCapacity)
            : this(vectorDimension, isHomogeneous, vectorFactory, initialCapacity, Int32.MaxValue)
        { }

        /// <summary>
        /// Creates a new <see cref="ManagedVectorBuffer{TVector, TComponent}" /> with
        /// initial capacity <paramref name="initialCapacity"/> for vectors of size
        /// <paramref name="vectorDimension"/>, including space for an extra component
        /// if <paramref name="isHomogeneous"/> is <see langword="true"/>. 
        /// </summary>
        /// <param name="vectorDimension">The size, or number of components, of each vector.</param>
        /// <param name="isHomogeneous">
        /// <see langword="true"/> if the vector is represented in homogeneous coordinates 
        /// (allowing affine transforms through matrix operations).
        /// </param>
        /// <param name="vectorFactory">
        /// A factory used to create vectors of type <typeparamref name="TVector"/>.
        /// </param>
        /// <param name="initialCapacity">The initial capacity for the buffer.</param>
        /// <param name="maximumCapacity">
        /// The maximum capacity of the vector buffer.
        /// </param>
        public ManagedVectorBuffer(Int32 vectorDimension, Boolean isHomogeneous,
                                   IBufferedVectorFactory<TVector, TComponent> vectorFactory,
                                   Int32 initialCapacity, Int32 maximumCapacity)
        {
            if (vectorDimension <= 0)
            {
                throw new ArgumentOutOfRangeException(
                    "vectorDimension", vectorDimension, "Parameter must be positive.");
            }

            if (initialCapacity < 0)
            {
                throw new ArgumentOutOfRangeException(
                    "initialCapacity", initialCapacity, "Parameter must be positive or zero.");
            }

            if (maximumCapacity <= 0)
            {
                throw new ArgumentOutOfRangeException(
                    "maximumCapacity", maximumCapacity, "Parameter must be positive.");
            }

            if (initialCapacity > maximumCapacity)
            {
                throw new ArgumentException("Initial capacity must be less than or " +
                                            "equal to maximum capacity.");
            }

            _maxSize = maximumCapacity;
            _vectorFactory = vectorFactory;

            // TODO: this will fail if TComponent is a reference type. 
            // Should it be constrained?
            _one = default(TComponent).One;

            _homogenousComponentCount = isHomogeneous ? 1 : 0;

            _vectorDimension = vectorDimension;
            Int32 bufferSize = initialCapacity * _vectorDimension + _homogenousComponentCount;
            _components = new TComponent[bufferSize];
        }

        #region IVectorBuffer<TVector,TComponent> Members
        /// <summary>
        /// Adds components to the buffer as a vector. Returns the resulting
        /// <typeparamref name="TVector"/> instance.
        /// </summary>
        /// <param name="v0">The first component which make up the vector.</param>
        /// <param name="v1">The second component which make up the vector.</param>
        /// <returns>
        /// The resulting vector after adding the given components.
        /// </returns>
        public TVector Add(TComponent v0, TComponent v1)
        {
            if (2 != VectorLength)
            {
                throw new ArgumentException("Number of components must match buffer "+
                                            "component storage.");
            }

            Int32 vectorIndex = addVector(v0, v1);

            return _vectorFactory.CreateBufferedVector(this, vectorIndex);
        }

        /// <summary>
        /// Adds components to the buffer as a vector. Returns the resulting
        /// <typeparamref name="TVector"/> instance.
        /// </summary>
        /// <param name="v0">The first component which make up the vector.</param>
        /// <param name="v1">The second component which make up the vector.</param>
        /// <param name="v2">The second component which make up the vector.</param>
        /// <returns>
        /// The resulting vector after adding the given components.
        /// </returns>
        public TVector Add(TComponent v0, TComponent v1, TComponent v2)
        {
            if (3 != VectorLength)
            {
                throw new ArgumentException(
                    "Number of components must match buffer component storage.");
            }

            Int32 vectorIndex = addVector(v0, v1, v2);

            return _vectorFactory.CreateBufferedVector(this, vectorIndex);
        }

        /// <summary>
        /// Adds an array of components to the buffer as a vector. Returns the resulting
        /// <typeparamref name="TVector"/> instance.
        /// </summary>
        /// <param name="components">The components which make up the vector.</param>
        /// <returns>
        /// The resulting vector after adding the given <paramref name="components"/>.
        /// </returns>
        public TVector Add(params TComponent[] components)
        {
            Int32 vectorLength = VectorLength;

            if (components.Length != vectorLength 
                && (components.Length + _homogenousComponentCount) != vectorLength)
            {
                throw new ArgumentException(
                    "Number of components must match buffer component storage.");
            }

            Int32 vectorIndex = addVector(components);

            return _vectorFactory.CreateBufferedVector(this, vectorIndex);
        }

        /// <summary>
        /// Adds an <see cref="IVector{TComponent}"/> to the buffer.
        /// </summary>
        /// <param name="item">The vector to add to the buffer.</param>
        /// <returns>The index of the added vector.</returns>
        public Int32 Add(IVector<TComponent> item)
        {
            return addVector(item.Components);
        }

        /// <summary>
        /// Clears the buffer of all vector instances.
        /// </summary>
        public void Clear()
        {
            _vectorIndexFreeList.Clear();

            Int32 count = Count;

            for (Int32 i = 0; i < count; i++)
            {
                _vectorIndexFreeList.AddLast(i);
            }
        }

        /// <summary>
        /// Copies the buffer to the given array.
        /// </summary>
        /// <param name="array">The array to copy the buffer to.</param>
        /// <param name="startIndex">The index of the buffer to start copying at.</param>
        /// <param name="endIndex">The index of the buffer to end copying at.</param>
        public void CopyTo(TVector[] array, Int32 startIndex, Int32 endIndex)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }

            if (startIndex < 0 || startIndex >= Count)
            {
                throw new ArgumentOutOfRangeException("startIndex", startIndex,
                                                      "Copy start index must be 0 or " +
                                                      "greater and less than " +
                                                      "the buffer's Count value.");
            }

            if (endIndex >= Count)
            {
                throw new ArgumentOutOfRangeException("endIndex", endIndex,
                                                      "Copy end index must be less than " +
                                                      "the buffer's Count value.");
            }

            Int32 length = (endIndex + 1) - startIndex;
            length = Math.Min(length, array.Length);

            for (Int32 destinationIndex = 0; destinationIndex < length; destinationIndex++)
            {
                TVector vector = _vectorFactory.CreateBufferedVector(
                    this, destinationIndex + startIndex);

                array[destinationIndex] = vector;
            }
        }

        /// <summary>
        /// Returns <see langword="true"/> if the buffer contains 
        /// the given <see cref="IVector{TComponent}"/>.
        /// </summary>
        /// <param name="item">The vector to check if the buffer contains.</param>
        /// <returns>
        /// <see langword="true"/> if the buffer contains <paramref name="item"/>;
        /// <see langword="false"/> otherwise.
        /// </returns>
        public Boolean Contains(IVector<TComponent> item)
        {
            // TODO: establish a behavior model for buffered vectors
            // What happens if a vector has an index which is on the removed list?
            //if (item is TVector)
            //{
            //    TVector vector = (TVector)item;

            //    if (ReferenceEquals(vector.GetBuffer(), this))
            //    {
            //        return true;
            //    }
            //}

            throw new NotImplementedException(
                "Vector lookup by coordinates not implemented.");
        }

        /// <summary>
        /// Gets the number of vectors in the buffer.
        /// </summary>
        public Int32 Count
        {
            get
            {
                Int32 length = VectorLength;
                return _nextVectorIndex - (length * _vectorIndexFreeList.Count) / length;
            }
        }

        /// <summary>
        /// Gets <see langword="true"/> if the buffer is read-only.
        /// </summary>
        public Boolean IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Gets or sets the maximum size of the buffer, in number of vectors.
        /// </summary>
        public Int32 MaximumSize
        {
            get { return _maxSize; }
            set
            {
                if (value <= 0)
                {
                    throw new ArgumentOutOfRangeException("value", value,
                                                          "Maximum size must be greater " +
                                                          "than 0");
                }

                if (value < _components.Length)
                {
                    throw new InvalidOperationException(
                        "Buffer size currently greater than proposed maximum.");
                }

                _maxSize = value;
            }
        }

        /// <summary>
        /// Gets or sets the <typeparamref name="TVector"/> at the given
        /// <paramref name="index"/>.
        /// </summary>
        /// <param name="index">The index of the vector to access.</param>
        /// <returns>
        /// The <typeparamref name="TVector"/> at <paramref name="index"/>.
        /// </returns>
        public TVector this[Int32 index]
        {
            get
            {
                checkIndex(index);

                return _vectorFactory.CreateBufferedVector(this, index);
            }
            set
            {
                checkIndex(index);

                setComponents(value.Components, index);
            }
        }

        public TComponent this[Int32 index, Int32 component]
        {
            get
            {
                checkIndex(index);

                Int32 vectorLength = VectorLength;

                if (component < 0 || component >= vectorLength)
                {
                    throw new ArgumentOutOfRangeException("component", component,
                        "Parameter component must be between 0 and VectorLength.");
                }

                return _components[index * vectorLength + component];
            }
        }

        public void Remove(Int32 index)
        {
            _vectorIndexFreeList.AddLast(index);
        }

        public event CancelEventHandler SizeIncreasing;

        public event EventHandler SizeIncreased;

        /// <summary>
        /// Gets the length, or number of components, in the vectors stored
        /// in the buffer.
        /// </summary>
        public Int32 VectorLength
        {
            get { return _vectorDimension + _homogenousComponentCount; }
        }

        public event EventHandler<VectorOperationEventArgs<TVector, TComponent>> VectorChanged;

        public Int32 Add(TVector vector)
        {
            return addVector(vector.Components);
        }

        public Boolean Contains(TVector item)
        {
            throw new NotImplementedException();
        }

        public IVectorFactory<TVector, TComponent> Factory
        {
            get { throw new NotImplementedException(); }
        }

        #endregion

        #region IEnumerable<IVector<TComponent>> Members

        public IEnumerator<TVector> GetEnumerator()
        {
            Int32 vectorCount = Count;

            for (Int32 i = 0; i < vectorCount; i++)
            {
                yield return _vectorFactory.CreateBufferedVector(this, i);
            }
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        protected void OnSizeIncreasing(ref Boolean cancel)
        {
            CancelEventHandler e = SizeIncreasing;

            if (e != null)
            {
                CancelEventArgs args = new CancelEventArgs();
                e(this, args);
                cancel = args.Cancel;
            }
        }

        protected void OnSizeIncreased()
        {
            EventHandler e = SizeIncreased;

            if (e != null)
            {
                e(this, EventArgs.Empty);
            }
        }

        #region Private helper methods

        private void checkIndex(Int32 index)
        {
            if (index < 0 || index >= Count)
            {
                throw new ArgumentOutOfRangeException("index",
                                                      index,
                                                      "Index must be between 0 " +
                                                      "and Count.");
            }
        }

        private Int32 addVector(TComponent v0, TComponent v1)
        {
            return addVector(v0, v1, default(TComponent));
        }

        private Int32 addVector(TComponent v0, TComponent v1, TComponent v2)
        {
            Boolean isNull = _isComponentValueType
                                 ? default(TComponent).Equals(v2)
                                 : Equals(default(TComponent), v2);

            Int32 componentCount = isNull ? 2 : 3;

            Int32 vectorIndex;

            if (_vectorIndexFreeList.Count > 0)
            {
                // Use free area in buffer to store vector
                vectorIndex = _vectorIndexFreeList.First.Value;
                _vectorIndexFreeList.RemoveFirst();
                Int32 componentsIndex = vectorIndex * componentCount;
                _components[componentsIndex] = v0;
                _components[componentsIndex + 1] = v1;
                if (componentCount == 3) _components[componentsIndex + 2] = v2;
            }
            else
            {
                // Expand storage if needed
                expandIfNeeded();

                vectorIndex = _nextVectorIndex;
                Int32 componentsIndex = vectorIndex * componentCount;
                _components[componentsIndex] = v0;
                _components[componentsIndex + 1] = v1;

                if (componentCount == 3)
                {
                    _components[componentsIndex + 2] = v2;
                }

                _nextVectorIndex += 1;
            }

            return vectorIndex;
        }

        private Int32 addVector(TComponent[] components)
        {
            Int32 vectorIndex;

            if (_vectorIndexFreeList.Count > 0)
            {
                // Use free area in buffer to store vector
                vectorIndex = _vectorIndexFreeList.First.Value;
                _vectorIndexFreeList.RemoveFirst();
            }
            else
            {
                // Expand storage if needed
                expandIfNeeded();

                vectorIndex = _nextVectorIndex;
                _nextVectorIndex += 1;
            }

            setComponents(components, vectorIndex);

            return vectorIndex;
        }

        private void expandIfNeeded()
        {
            if (_nextVectorIndex >= _components.Length / VectorLength)
            {
                expandStorage();
            }
        }

        private void expandStorage()
        {
            Boolean cancel = false;

            OnSizeIncreasing(ref cancel);

            if (cancel)
            {
                return;
            }

            Int64 expandedLength = _components.Length * 2;

            if (expandedLength > (Int64)MaximumSize * VectorLength)
            {
                expandedLength = MaximumSize * VectorLength;
            }

            if (expandedLength == _components.Length)
            {
                throw new InvalidOperationException(
                    "Cannot expand buffer past MaximumSize.");
            }

            TComponent[] copy = new TComponent[expandedLength];
            Array.Copy(_components, copy, _components.Length);
            _components = copy;

            OnSizeIncreased();
        }

        private void setComponents(TComponent[] components, Int32 vectorIndex)
        {
            Int32 vectorLength = VectorLength;
            Int32 dstOffset = vectorIndex * vectorLength;
            Int32 componentCount = components.Length;

            Array.Copy(components, 0, _components, dstOffset, componentCount);

            if (componentCount == vectorLength - 1)
            {
                Int32 homogenousComponentIndex = dstOffset + componentCount;
                _components[homogenousComponentIndex] = _one;
            }
        }
        #endregion
    }
}
